home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 262_01 / symtbl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-03-28  |  8.9 KB  |  249 lines
  1. /*********************************************************
  2.  *             Symbol Table Manipulation Package         *
  3.  *               Robert Ramey     21 Sept 1986           *
  4.  *********************************************************/
  5.  
  6. #include <stdio.h>
  7.  
  8. /***********************************************************
  9. These routines use a character pointer to symbols and data.
  10. Pointers to symbol table entries point to the character
  11. string that is the symbol itself.  Pointer returned by symdat
  12. are character pointers to the stored data structure.  These
  13. should be recast to the appropriate structure pointer before
  14. being used.  All other pointers are not expected to be used
  15. by the calling programs except as character pointers so no
  16. casting should be necessary.
  17. **********************************************************/
  18. typedef char SYMBOLENTRY;
  19.  
  20. struct _symtbl {    /*structure for symbol table data */
  21.     int _element_size; /*size of data not includeing links nor*/
  22.               /*symbol itself */
  23.     int _hash_factor; /*number of chains of symbols */
  24.     SYMBOLENTRY *_hash_address[1]; /*address of start of chain */
  25. };
  26. typedef struct _symtbl SYMBOLTABLE;
  27.  
  28. /***********************************************************
  29. symmk - used to initialize a symbol table.  If there is not
  30. enough memory available to allocate a symbol table structure
  31. symmk will return NULL.  Otherwise, it will return a pointer
  32. to the created symbol table structure.  This pointer is used
  33. on subsecuent calls to insert, lookup and delete symbols from
  34. the table.  This permits multiple symbol tables with in a 
  35. program all using the same code.
  36. ************************************************************/
  37.  
  38. SYMBOLTABLE  *
  39. symmk(element_size,hash_factor)
  40. int element_size;   /*The amount of data to be associated
  41.              *with each symbol of the table */
  42. register  int hash_factor;/*The number of chains of symbols to be
  43.              *created */
  44. {
  45.     SYMBOLTABLE *stptr;
  46.     register SYMBOLENTRY **st_entry;
  47.  
  48.     /* get space for symbol table */
  49.     stptr = (SYMBOLTABLE *) /* cast to symbol table ptr*/
  50.         /* size of first two entries in SYMBOLTABLE structure*/
  51.         malloc(sizeof(int) * 2 +
  52.         /* size of hash table */
  53.         sizeof(SYMBOLENTRY *) * hash_factor);
  54.     if(stptr == NULL)
  55.         return NULL;    /* Not enough space for table */
  56.     stptr->_element_size = element_size;
  57.     stptr->_hash_factor = hash_factor;
  58.     st_entry = stptr->_hash_address + hash_factor;
  59.     while(hash_factor--)
  60.         *--st_entry = NULL;
  61.     return stptr;
  62. }
  63. /***************************************************************
  64. _nxtsym - returns address of pointer to next entry in chain
  65. ****************************************************************/
  66. SYMBOLENTRY **
  67. _nxtsym(st_entry)
  68. SYMBOLENTRY *st_entry;
  69. {
  70.     return st_entry - 2 * sizeof(SYMBOLENTRY *) ;
  71. }
  72. /****************************************************************
  73. _prvsym - returns address of pointer to previous entry in chain
  74. *****************************************************************/
  75. SYMBOLENTRY **
  76. _prvsym(st_entry)
  77. SYMBOLENTRY *st_entry;
  78. {
  79.     return st_entry - sizeof(SYMBOLENTRY *);
  80. }
  81. /************************************************************
  82. hash - Returns an index into the hash table.
  83. *************************************************************/
  84. int
  85. _hash(stptr,symbol)
  86. SYMBOLTABLE *stptr;
  87. register char *symbol;
  88. {
  89.     /* accumlate hash total from sum of characters in symbol */
  90.     register int hash_total;
  91.     do{
  92.         hash_total += *symbol++;
  93.     }
  94.     while(*symbol);
  95.     return hash_total % stptr->_hash_factor;
  96. }
  97. /****************************************************************
  98. symdat - returns address of data given symbol pointer as argument.
  99. Note that address is cast as a character pointer.  It is the 
  100. callers responsability to recast this as the appropriate structure
  101. pointer if necessary.
  102. ******************************************************************/
  103. char *
  104. symdat(stptr, st_entry)
  105. SYMBOLTABLE *stptr;
  106. SYMBOLENTRY *st_entry;
  107. {
  108.     return
  109.     st_entry - stptr->_element_size - 2 * sizeof(SYMBOLENTRY *);
  110. }
  111. /*****************************************************************
  112. symadd - add a symbol with its corresponding data to symbol table.
  113. Returns NULL if there was not enough memory to add symbol.
  114. Otherwise returns pointer to symbol string in table.
  115. ******************************************************************/
  116. SYMBOLENTRY *
  117. symadd(stptr,symbol)
  118. SYMBOLTABLE *stptr; /*pointer to symbol table to be used */
  119. char *symbol;   /*pointer to symbol string and data*/
  120. {
  121.     int size, hash_total;
  122.     register SYMBOLENTRY *st_entry;
  123.     SYMBOLENTRY *st_head;
  124.  
  125.     /* figure start of chain */
  126.     hash_total = _hash(stptr,symbol);
  127.  
  128.     /*get space for symbol table entry */
  129.     size = stptr->_element_size + 2 * sizeof(SYMBOLENTRY *);
  130.  
  131.     st_entry = malloc(strlen(symbol) /* size of symbol itself */
  132.         + size /* for data and pointers in table */
  133.         + sizeof(char));    /* Null terminator on symbol */
  134.                      /* and previous entry */
  135.     if(!st_entry)
  136.         return NULL;    /* return if not enough space */
  137.  
  138.     st_entry += size;   /* remember symbol table entry */
  139.         /* doesn't point to beginning of data but to */
  140.         /*  symbol string itself */
  141.  
  142.     /* add new entry to start of chain */
  143.  
  144.     /*before creating new element update reverse pointer on next */
  145.     if(st_head = stptr->_hash_address[hash_total])
  146.         *(_prvsym(st_head)) = st_entry;
  147.  
  148.     /* first pointer to next element */
  149.     *(_nxtsym(st_entry)) = st_head;
  150.  
  151.     /* pointer to previous element */
  152.     *(_prvsym(st_entry)) =
  153.         (SYMBOLENTRY *)(stptr->_hash_address + hash_total)
  154.         + 2 * sizeof(SYMBOLENTRY *);
  155.         /* The + 2 is to permit nxtsym function when arg */
  156.         /* is the first element */
  157.  
  158.     /* finally add symbol string to table */
  159.     strcpy(st_entry,symbol);
  160.  
  161.     /* modify pointer to start of chain */
  162.     stptr->_hash_address[hash_total] = st_entry;
  163.  
  164.     return st_entry;
  165. }
  166. /************************************************************
  167. symlkup - find a symbol in a symbol table.  Returns NULL if 
  168. symbol not found.  Otherwise returns pointer to the symbol
  169. string.
  170. *************************************************************/
  171. SYMBOLENTRY *
  172. symlkup(stptr, symbol)
  173. SYMBOLTABLE *stptr;
  174. char *symbol;
  175. {
  176.     SYMBOLENTRY *symptr;
  177.     unsigned int hash_total;
  178.     /* figure out where start of chain is */
  179.     hash_total = _hash(stptr, symbol);
  180.     
  181.     symptr = stptr->_hash_address[hash_total];
  182.     while(symptr){
  183.         if(!strcmp(symbol,symptr))
  184.             return symptr;
  185.         symptr = *_nxtsym(symptr);
  186.     }
  187.     return NULL;
  188. }
  189. /*************************************************************
  190. symdel - Delete a symbol and its data and return space to system.
  191. We make no tests that the argument is actually in the table.
  192. So take care that argument is pointer to current symbol in table.
  193. That is, the argument must have been previously retrieved via
  194. symadd, symlkup, first, or next.  If you forget and simply pass
  195. a pointer to a string as an argument you can be sure of getting
  196. real problems.  No value is returned.
  197. ***************************************************************/
  198. void
  199. symdel(stptr,st_entry)
  200. SYMBOLTABLE *stptr;
  201. SYMBOLENTRY *st_entry;
  202. {
  203.     *_nxtsym(*_prvsym(st_entry)) = *_nxtsym(st_entry);
  204.     *_prvsym(*_nxtsym(st_entry)) = *_prvsym(st_entry);
  205.     free(st_entry -
  206.         stptr->_element_size -
  207.          2 * sizeof(SYMBOLENTRY *));
  208.     return;
  209. }
  210. /******************************************************************
  211. symdmp - Used to sequentially retrieve all symbols in table. The
  212. pointer to the "first" symbol is retrieved with symdmp(stptr, 0) while
  213. pointers to subsequent symbols are retrieved with symdmp(sptr, !=0).
  214. It is garenteed that each and every symbol will be retrieved
  215. exactly once.  When there are no more symbols to be retrieved
  216. NULL will be returned.
  217. *******************************************************************/
  218. SYMBOLENTRY *
  219. symdmp(stptr,initial)
  220. SYMBOLTABLE *stptr;
  221. unsigned int initial;
  222. {
  223.     static SYMBOLENTRY *current_symbol;
  224.     static int hash_count;
  225.     if(!initial){
  226.         hash_count = stptr->_hash_factor;
  227.         current_symbol = NULL;
  228.     }
  229.     else
  230.         current_symbol = *_nxtsym(current_symbol);
  231.     while(!current_symbol && hash_count)
  232.         current_symbol = stptr->_hash_address[--hash_count];
  233.     return current_symbol;
  234. }
  235. /********************************************************************
  236. symrmv - delete an entire symbol table and return space to system.
  237. *********************************************************************/
  238. void
  239. symrmv(stptr)
  240. SYMBOLTABLE *stptr;
  241. {
  242.     SYMBOLTABLE *current_symbol;
  243.     while(current_symbol = symdmp(stptr, 0))
  244.         symdel(stptr, current_symbol);
  245.     free(stptr);
  246.     return;
  247. }
  248. count)
  249.